package com.faiz.algorithm;

import java.util.*;

public class Dijkstra2 {

    // 图数组
    int[][] graph;
    // 邻接链表
    List<Integer>[] adjs;

    /**
     * 内部类，用于存储从源节点到当前节点的距离
     */
    class State {
        // 图节点的 id
        int id;
        // 从 start 节点到当前节点的距离
        int distFromStart;

        State(int id, int distFromStart) {
            this.id = id;
            this.distFromStart = distFromStart;
        }
    }

    /**
     * 返回信号传播到所有节点的时间
     *
     * @param times times数据
     * @param n     节点数量
     * @param k     源节点
     * @return 传播时间
     */
    public int networkDelayTime(int[][] times, int n, int k) {
        // 本题使用Dijkstra算法进行解决
        init(times, n);
        int[] distTo = dijkstra(k, n);
        int res = getMax(distTo);
        return res == Integer.MAX_VALUE ? -1 : res;
    }

    private int getMax(int[] nums) {
        int max = Integer.MIN_VALUE;
        for (int num : nums) {
            max = Integer.max(max, num);
        }
        return max;
    }

    private void init(int[][] times, int n) {
        initGraph(times, n);
        initAdjs(n);
    }

    /**
     * 初始化图数组
     *
     * @param times
     * @param n  节点个数/数组长度
     */
    private void initGraph(int[][] times, int n) {
        graph = new int[n][n];
        // 将graph值初始为无穷
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                graph[i][j] = Integer.MAX_VALUE;
            }
        }

        // 向graph中填写数据
        for (int[] nums : times) {
            graph[nums[0] - 1][nums[1] - 1] = nums[2];
        }
    }

    /**
     * 初始话邻接链表
     *
     * @param n 节点个数/数组长度
     */
    private void initAdjs(int n) {
        adjs = new List[n];
        for (int i = 0; i < n; i++) {
            adjs[i] = new ArrayList<>();
            for (int j = 0; j < n; j++) {
                if (graph[i][j] != Integer.MAX_VALUE) {
                    adjs[i].add(j);
                }
            }
        }
    }

    /**
     * dijkstra算法
     *
     * @param start 源节点（起始节点）
     * @param n     节点数量
     * @return 返回源节点
     */
    public int[] dijkstra(int start, int n) {

        int[] distTo = new int[n];
        Queue<State> queue = new PriorityQueue<>(Comparator.comparingInt(x -> x.distFromStart));
        queue.offer(new State(start - 1, 0));
        Arrays.fill(distTo, Integer.MAX_VALUE);
        distTo[start - 1] = 0;
        while (!queue.isEmpty()) {
            State cur = queue.poll();
            int curDistance = cur.distFromStart;
            int curId = cur.id;
            for (int adj : adj(curId)) {
                if (distTo[adj] > curDistance + weight(curId, adj)) {
                    distTo[adj] = curDistance + weight(curId, adj);
                    queue.offer(new State(adj, curDistance + weight(curId, adj)));
                }
            }
        }
        return distTo;
    }

    /**
     * 获取某一点到另一点的权重
     *
     * @param from 从
     * @param to   至
     * @return 权重
     */
    public int weight(int from, int to) {
        return graph[from][to];
    }

    /**
     * 获取节点s的可达邻近节点
     *
     * @param s 当前节点
     * @return 当前节点s的邻近节点
     */
    public List<Integer> adj(int s) {
        return adjs[s];
    }

    public static void main(String[] args) {
        int[][] times = {{2, 1, 1}, {2, 3, 1}, {3, 4, 1}};
        Dijkstra2 dijkstra2 = new Dijkstra2();
        int i = dijkstra2.networkDelayTime(times, 4, 2);
        System.out.println(i);
    }

}
